The present invention relates generally to decoding received vectors encoded with a linear block forward error correction (FEC) code having a parity check matrix comprising multiple distinct pattern regions.
It is known to encode message words of a digital message with an FEC code prior to sending the message through a transmission medium. Among other benefits, the FEC encoding allows a decoder at a receiver to detect and correct errors in the received vectors of the transmitted message.
FIG. 1 illustrates an example of a prior art system 100 comprising an encoder 104, a source 108, a receiver 112, and a decoder 116. As shown, the encoder 104 can receive a message stream 102 comprising a plurality of digital message words m each of which comprises k bits m1, m2, . . . , mk. The encoder 104 can encode each message word m into a codeword c, producing a codeword stream 106. Each of the codewords c in the codeword stream 106 can comprise n bits c1, c2, . . . , cn, where n is greater than k. The source 108 can send the codeword stream 106 through a transmission medium 110 to a receiver 112, which receives the transmitted codeword stream 106 as a received vector stream 114.
Distortions and other errors can be introduced into the codewords c by the circuitry of the source 108, the transmission medium 110, and/or the circuitry of the receiver 112, which can render uncertain the values of the bits c1, c2, . . . , cn at the receiver 112. The codewords c are thus identified at the output of the receiver 112 as received vectors r, and the bits are referred to as probabilities r1, r2, . . . , rn. The receiver 112 is thus shown in FIG. 1 as providing a stream of received vectors r to a decoder 116. The decoder 116 decodes the probabilities r1, r2, . . . , rn of each received vector r into the bits c1, c2, . . . , cn of the codewords c from which the decoder 116 can output 118 as a stream 102′ of decoded message words m, which should be the same as the original message words m in the stream 102.
The source 108 can be any device that sends digital data to a receiver. For example, the source 108 can be a radio frequency (RF) wireless transmitter, a node in a computer or communications network, a data source such as a data memory (e.g., a digital storage disk), or the like. The receiver 112 can be any type of receiver for receiving data from such a source 108.
Linear block codes are a class of FEC codes. A particular linear block FEC code can be defined by a generator matrix G and/or a corresponding parity check matrix H. The generator matrix G is an n row by k column matrix, which encodes each k-bit message word m in a set of possible message words into a unique n-bit codeword c. For example, for each possible k-bit message word m, multiplication of the message word m by the generator matrix G yields a unique n-bit codeword c. The parity check matrix H is an n−k row by n column matrix. Multiplication of a valid codeword c by the parity check matrix H is zero. The parity check matrix H can thus be used to decode probabilities r1, r2, . . . , rn of the received vectors r that correspond to codewords c encoded with a linear block FEC code.
FIG. 2 illustrates a simplified example of a parity check matrix H 200 in which the parity check matrix H 200 is a two row by four column matrix. There is a column C1, C2, C3, C4 for each bit c in a codeword c, and the matrix H 200 thus corresponds to four bit codewords c. Each row R1, R2 of the matrix H 200 defines a parity check calculation for determining whether current estimated values of the probabilities r1, r2, r3, r4 of a received vector r that corresponds to a codeword c being decoded are likely correct.
FIG. 3 illustrates a Tanner-Graph based decode module 300 that corresponds to the parity check matrix H 200. As is known, a Tanner-Graph based decode module of a parity check matrix H has the following characteristics: there is a variable node (VN) for each column of the matrix H and thus each probability r1, r2, r3, . . . , rn of a received vector r being decoded; there is a check node (CN) for each row of the matrix H; each VN calculates a new estimated value (EV) of one of the probabilities r1, r2, r3, . . . , rn of the received vector r using the current EV and one or more parity check results from check-node-to-variable-node messages (C-VMs) from one or more check nodes (CN); each VN sends its new EV to one or more CNs via a variable-node-to-check-node message (V-CM); each CN performs a parity check calculation defined by one of the rows of the matrix H using EVs received from VNs in the V-CMs; each CN sends its parity check result to one or more VNs via a C-VM; and there is a connection for the V-CMs and C-VMs between each VN and CN that correspond to a “one” in the parity check matrix H.
Accordingly, in FIG. 3, the Tanner-Graph decode module 300 comprises VN1 302, VN2 304, VN3 306, VN4 308, which correspond respectively to columns C1, C2, C3, C4 of the matrix H 200 of FIG. 2 and thus to the probabilities r1, r2, r3, . . . , rn of a received vector r. The module 300 likewise comprises CN1 312, CN2 314, which correspond respectively to rows R1, R2. As also shown in FIG. 3, there is a connection (also known as an “edge”) 322, 324, 326, 328, 330 between the VNs 302, 304, 306, 308 and the CNs 312, 314 for each “one” in the parity check matrix H 200. That is, due to the “one” at R1, C1 of the matrix H 200 in FIG. 2, there is a connection 322 between VN1 302 and CN1 312 in FIG. 3. There is also a connection 324 between VN2 304 and CN1 312 and a connection 326 between VN4 308 and CN1 312 due to the “ones” in the matrix H 200 at R1, C2 and R1, C4. There are likewise connections 328 and 330 between VN2 304 and CN2 314 and VN3 306 and CN2 314 due to the “ones” in the matrix H 200 at R2, C2 and R2, C3.
The decoder 116 of FIG. 1 can be configured in accordance with the Tanner-Graph decode module 300 of FIG. 3. In operation, for each received vector r in a received vector stream 114 of FIG. 1, the VNs 302, 304, 306, 308 provide initial estimated values EVs of the probabilities r1, r2, r3, and r4 of the received vector r (in the simplified example illustrated in FIGS. 2 and 3 the number of bits c in a codeword c and thus the number of probabilities r in a received vector r is four) in V-CMs to the CNs 312, 314 through connections 322, 324, 326, 328, 330. Each CN 312, 314 then performs a parity check calculation using the EVs and provides the results in C-VMs to the VNs 302, 304, 306, 308. The VNs 302, 304, 306, 308 then use the parity check calculations in the C-VMs to calculate new EVs for the probabilities r1, r2, r3, and r4 of the received vector r and provide the new EVs in new V-CMs to the CNs 312, 314 after which each CN 312, 314 again performs a parity check calculation using the new EVs and provides the results of the parity check calculations in new C-VMs to the VNs 302, 304, 306, 308. The foregoing iteration of calculations of new EVs by the VNs 302, 304, 306 308 followed by the calculation of new parity checks by the CNs 312, 314 can be repeated until the new EVs for the probabilities r1, r2, r3, and r4 of the received vector r are believed to be the correct values of the bits c1, c2, c3, and c4 of the corresponding codeword c or until the iterations are stopped for other reasons.
In the example illustrated in FIG. 3, each V-CM and C-VM is identified by a subscript indicating the sending and receiving nodes. Thus, V-CM11 is a message sent from VN1 302 to CN1 312 that contains a new EV for the first probability r1 of the received vector r calculated by VN1 302, and C-VM11 is a message sent from CN1 312 to VN1 302 that contains the results of a parity check calculation by CN1. Similarly, V-CM21 is a message sent from VN2 304 to CN1 312 that contains a new EV for the second probability r2 of the received vector r calculated by VN2 304, and C-VM12 is a message sent from CN1 312 to VN2 304 that contains the results of the parity check calculation by CN1 312. Likewise, V-CM22 is a message sent from VN2 304 to CN2 314 that contains the new EV for the second probability r2 of the received vector r calculated by VN2 304, and C-VM22 is a message sent from CN2 314 to VN2 304 that contains the results of a parity check calculation by CN2 314. The messages V-CM32 and C-VM23 follow the same pattern: V-CM32 is a message sent from VN3 306 to CN2 314 that contains a new EV for the third probability r3 of the received vector r calculated by VN3 306, and C-VM23 is a message sent from CN2 314 to VN3 306 that contains the results of a parity check calculation by CN2 314. The messages V-CM41 and C-VM14 also follow the same pattern: V-CM41 is a message sent from VN4 308 to CN1 312 that contains a new EV for the fourth probability r4 of the received vector r calculated by VN4 308, and C-VM14 is a message sent from CN1 312 to VN4 308 that contains the results of a parity check calculation by CN1 312.
Traditionally, a Tanner-Graph based configuration of the probability decoder 116 is configured such that, at each iteration, CNs 312, 314 do not perform their parity check calculations until all VNs 302, 304, 306, 308 have sent all of the messages V-CM, and VNs 302, 304, 306, 308 do not thereafter perform their calculations in the next iteration until all CNs 312, 314 have sent all of the messages C-VM. Recently, however, various configurations of digital processing electronics have been developed for improving the efficiency of Tanner-Graph based configurations of a probability decoder 116. For example, each VN and CN can be implemented in one or more processors that are connected serially and/or in parallel to perform efficiently the calculations of the VNs and CNs. Processing efficiency has been achieved in some cases by tailoring the interconnections of such processors to particular patterns of the “ones” in the parity check matrix H. This has allowed, for example, the Tanner-Graph implementation to be based on a sub-set of the columns and/or rows of the parity check matrix H and then repeatedly applied to the parity check matrix H until all of the columns and/or rows have been processed. Some FEC codes, however, have a parity check matrix H comprising multiple regions in which the patterns of “ones” have different pattern characteristics. Prior configurations of Tanner-Graph based probability decoding modules have not efficiently addressed decoding such FEC codes. Embodiments of the present invention provide efficient decoding of FEC codes in which the parity check matrix H comprises multiple regions in which the pattern of “ones” in at least two of those regions have different pattern characteristics.